package leetcode.tree;

/**
 * @author wangmaolin1
 * @date 2023/11/11 23:00
 */
public class _700 {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        int diff = root.val - val;
        if (diff > 0) {
            return searchBST(root.left, val);
        } else if (diff < 0) {
            return searchBST(root.right, val);
        }
        return root;
    }

    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 找到空位置插入新节点
        if (root == null) return new TreeNode(val);
        // if (root.val == val)
        //     BST 中一般不会插入已存在元素
        if (root.val < val)
            root.right = insertIntoBST(root.right, val);
        if (root.val > val)
            root.left = insertIntoBST(root.left, val);
        return root;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode rightMin = findMin(root.right);
            root.right = deleteNode(root.right, rightMin.val);
            rightMin.left = root.left;
            rightMin.right = root.right;
            root = rightMin;
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            root.left = deleteNode(root.left, key);
        }
        return root;
    }

    private TreeNode findMin(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode temp = root;
        while (temp.left != null) {
            temp = temp.left;
        }
        return temp;
    }


}
